#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int graph[6][6]; 
int time_slots[6]; 
int num_projects = 6;
// 初始化邻接矩阵
void Initgraph() {
	for (int i = 0; i < num_projects; i++) {
		for (int j = 0; j < num_projects; j++) {
			graph[i][j] = 0; 
		}
	}
}

// 构建冲突图
void CreatGraph(int athletes, int athlete_projects[][6], int num_projects_athlete[]) {
	Initgraph();
	for (int k = 0; k < athletes; k++) {
		for (int i = 0; i < num_projects_athlete[k]; i++) {
			for (int j = i + 1; j < num_projects_athlete[k]; j++) {
				int p1 = athlete_projects[k][i];
				int p2 = athlete_projects[k][j];
				graph[p1][p2] = 1; 
				graph[p2][p1] = 1; 
			}
		}
	}
}
// 检查项目在时间段中的可用性
int is_available(int project, int time_slot) {
	for (int i = 0; i < num_projects; i++) {
		if (graph[project][i] == 1 && time_slots[i] == time_slot) {
			return 0; 
		}
	}
	return 1; 
}

// 尝试为所有项目分配时间段
int assign_time_slots(int project) {
	if (project == num_projects) {
		return 1; 
	}
	
	for (int time_slot = 0; time_slot < num_projects; time_slot++) {
		if (is_available(project, time_slot)) {
			time_slots[project] = time_slot; 
			
			if (assign_time_slots(project + 1)) {
				return 1; 
			}
			
			time_slots[project] = -1; 
		}
		}
	return 0; 
}
// 打印安排的时间段
void print_schedule() {
	printf("运动会计划：\n");
	for (int t = 0; t < num_projects; t++) {
		printf("时间段 %d: ", t + 1);
		for (int i = 0; i < num_projects; i++) {
			if (time_slots[i] == t) { 
				printf("项目 %c ", 'A'+i);
			}
		}
		printf("\n");
	}
}

int main() {
	int n9u3m_ath = 5;
	int a9t3hlete_pro[5][6] = {
		{0, 1, 4}, 
		{2, 3},    
		{2, 4, 5}, 
		{3, 5, 0}, 
		{1, 5}     
	};
	int n9u3m_projects_athlete[5] = {3, 2, 3, 3, 2}; 
	
	CreatGraph(n9u3m_ath, a9t3hlete_pro, n9u3m_projects_athlete);
	
	for (int i953 = 0; i953 < num_projects; i953++) {
		time_slots[i953] = -1; 
	}
	
	if (assign_time_slots(0)) {
		print_schedule();
	} else {
		printf("没有最好的方案\n");
	}
	
	return 0;
}


